Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work (Efroni et al., 2018), multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.

The authors first show a negative result that soft-policy updates using the multi-step greedy policies do not guarantee policy improvement. Then the authors proposed an algorithm that uses cautious soft updates (only update to the kappa greedy policy only when assured to improve, otherwise stay with one-step greedy policy) and show that it converges to the optimal policy. Lastly the authors studied hard updates by extending APIs to multi-step greedy policy setting. Comments: 1. Theorem 2 presents an interesting and surprising result. Though the authors presented the example in the proof sketch, but I wonder if the authors could provide more intuitions behind this? Based on the theorem, for multi-step greedy policy, it seems that h needs to be bigger than 2. So I suspect that h 2 will still work (meaning there could exist small alpha)? Obviously h 1 works, but then why when h 3, the soft-update suddenly stops working unless alpha is exactly equal to 1? I would expect that one would require larger alpha when h gets larger.

Multiple-step lookahead policies have demonstrated high empirical competence in Reinforcement Learning, via the use of Monte Carlo Tree Search or Model Predictive Control. In a recent work (Efroni et al., 2018), multiple-step greedy policies and their use in vanilla Policy Iteration algorithms were proposed and analyzed. In this work, we study multiple-step greedy algorithms in more practical setups. We begin by highlighting a counter-intuitive difficulty, arising with soft-policy updates: even in the absence of approximations, and contrary to the 1-step-greedy case, monotonic policy improvement is not guaranteed unless the update stepsize is sufficiently large. Taking particular care about this difficulty, we formulate and analyze online and approximate algorithms that use such a multi-step greedy operator.